When keeping secret information such as a secret key used for encryption, there are the threat of “losing and damaging” it and the threat of having it “stolen”. For the former case, it is effective to generate a backup copy of the secret information. However, making the copy may increase a risk of facing the latter threat. As one of information security techniques for overcoming such issue, there is a secret distribution method depicted in Non-Patent Documents 1 and 2.
The secret distribution method is characterized to generate a plurality of pieces of distributing information acquired by distributing secret information, keep those separately, and generate it possible to uniquely restore the original secret information by gathering a preset number of pieces of distributed information among the kept distributed information. However, it is impossible to restore the secret information by gathering the distributed information other than those pieces. Hereinafter, in this Description, the number of pieces of distributed information is defined as “n” pieces, and each of n-pieces of distributed information is identified by using identifiers of 1 to n.
With the secret distribution method, a set of distributed information with which the secret information can be restored can be defined with “Γ” that is a set group of the distributed information of an access structure. The access structure “Γ” is a set group that has, as elements thereof, a set of identifiers of the minimum number of pieces of distributed information with which the secret information can be restored. With the secret distribution method having the access structure “Γ”, “a set w of the distributed information is capable of restoring the secret information” means that there is “V” that satisfies a following Expression 1 for a set W of the identifiers of the distributed information corresponding to the set w. Further, the set W of the identifiers of the distributed information having a character satisfying Expression 1 is defined as an access set of “Γ”.VεΓ and VW  [Expression 1]
As the secret distribution method, there is a method called a (k, n) threshold scheme. The (k, n) threshold scheme is a secret distribution method which distributes secret information into n-pieces of distributed information, and uses k (n>K) pieces of distributed information among the n-pieces of distributed information to restore the secret information. Note that “k” in the (k, n) threshold scheme corresponds to V of Expression 1 described above. An access structure “Γ” used in the (k, n) threshold scheme is defined by a set group shown in Expression 2. The access structure “Γ” has two characters, i.e., “secret information cannot be restored at all with less than k-pieces of distributed information among the n-pieces of distributed information” and “secret information can be restored uniquely from the k-pieces or more pieces of distributed information”. Hereinafter, issues when restoring the secret information with the secret distribution method will be investigated.Γ={V|V{1,2, - - - ,n} and number of elements of V is k}  [Expression 2]
When restoring the secret information, it is necessary to collect the required number of pieces of distributed information for restoring the secret information from a plurality of recording modules which keep the individual distributed information. In this case, it is not perfectly sure that the requested side of the distributed information gives the distributed values, specifically, the distributed information kept in the recording modules, to the restorer without manipulation. That is, there may be a case where the distributed information in the recording modules is handed over to the restorer after being manipulated.
The “manipulation” herein means not only a case where an administrator to which the distributed information is given manipulates the distributed information intentionally but also a case where the distributed information is manipulated against the intention of the administrator of the distributed information. As examples of the case where the distributed information is manipulated against the intention of the administrator, there are cases where the distributed information is manipulated because of a fault generated in a device which stores the distributed information to the recording modules, cases where the distributed information is manipulated due to an operation error of the administrator, etc.
When the secret information is restored by using the manipulated distributed information, values of the restored secret information may, become different from values of the original secret information. Thus, as the secret distribution method, desired is a method which can detect with a high probability that there are manipulated values contained in the distributed information used for restoration.
Further, a means for selecting the distributed information varies depending on the operation forms. Therefore, it is desired to have a high detection rate of the manipulated values regardless of the types of probability distributions upon which the distributed information is selected.
As the techniques for overcoming such issues, the techniques depicted in Non-Patent Documents 3 to 7 are known.
Non-Patent Document 3 discloses a (k, n) threshold scheme which can detect a cheating of altering merely (k−1) pieces of distributed information by referring to (n−1) pieces of distributed information with a probability of (1−ε) regardless of the types of the probability distribution upon which the secret information is selected. With the method depicted in Non-Patent Document 3, assuming that the secret information is a set containing s-pieces of elements, the distributed information is a set containing the number of elements shown with Expression 3. Note that “n” and “k” correspond to “k” and “n” of the (k, n) threshold scheme.Number of elements=((s−1)(k−1)/ε+k)2  [Expression 3]
Non-Patent Document 4 discloses a (k, n) threshold scheme which can detect cheating of manipulating merely (k−1) pieces of distributed information by referring to (k−1) pieces of distributed information with a probability of (1−ε) on condition that the secret information is selected based upon a uniform probability distribution. With the method depicted in Non-Patent Document 4, assuming that the secret information is a set containing s-pieces of elements, the distributed information is a set containing the number of elements shown with Expression 4. Note that “k” corresponds to “k” of the (k, n) threshold scheme.Number of elements=(1+(s−1)/ε)  [Expression 4]
Non-Patent Document 5 discloses a (n, n) threshold scheme which can detect cheating of manipulating merely (k−1) pieces of distributed information by referring to (k−1) pieces of distributed information with a probability of (1ε) regardless of the types of the probability distribution upon which the secret information is selected. With the method depicted in Non-Patent Document 5, assuming that the secret information is a set containing s-pieces of elements, the distributed information is a set containing the number of elements shown with Expression 5. The (n, n) threshold scheme is a secret distribution method which distributes secret information into n-pieces of distributed information, and uses the n-pieces of distributed information to restore the secret information. Note that “n” of the (n, n) threshold scheme of the secret distribution method corresponds to “k” mentioned above.Number of elements=s/ε2  [Expression 5]
Non-Patent Document 6 discloses a (k, n) threshold scheme which can detect cheating of manipulating merely (k−1) pieces of distributed information by referring to (n−1) pieces of distributed information with a probability of (1ε) regardless of the types of the probability distribution upon which the secret information is selected. With the method depicted in Non-Patent Document 6, when the secret information is a set containing s-pieces of elements and s satisfies s≦1/ε, the distributed information is a set containing the number of elements shown with Expression 6. Note that “k” corresponds to “k” of the (k, n) threshold scheme.Number of elements=s2/ε  [Expression 6]
Non-Patent Document 7 discloses a (k, n) threshold scheme which can detect cheating of manipulating merely (k−1) pieces of distributed information by referring to (n−1) pieces of distributed information with a probability of (1ε) regardless of the types of the probability distribution upon which the secret information is selected. With the method depicted in Non-Patent Document 7, when the secret information is a set containing s-pieces of elements and s satisfies s≦1/ε, the distributed information is a set containing the number of elements shown with Expression 7. Note that “k” corresponds to “k” of the (k, n) threshold scheme.Number of elements=s×(log(s))k+1/ε  [Expression 7]
Patent Document 1 related to the secret distribution method as described above discloses a structure which allocates distributed information generated by a (k+t, n+t) method for each of n-pieces of administrator devices. Patent Document 2 discloses a structure which acquires a plurality of optimum allocated maps for a general access structure by integer programming.
Patent Document 3 discloses a data protection method and the like which store generated distributed information by further encrypting it with a public key, restore the distributed information with a secret key, and then restore secret information that is the original data. Patent Document 4 discloses a distributed information restoring system and the like with which a distributed information managing device conceals and saves distributed information with random numbers according to a request from an information utilization device that saves the random numbers.    Patent Document 1: Japanese Unexamined Patent Publication 2002-217891    Patent Document 2: Japanese Unexamined Patent Publication 2004-336577    Patent Document 3: Japanese Unexamined Patent Publication 2008-097591    Patent Document 4: Japanese Unexamined Patent Publication 2008-250931    Non-Patent Document 1: Adi Shamir, “How to share a secret”, Comm. ACM, 22(11), 612-613 (1979)    Non-Patent Document 2: J. Benaloh and J. Leichter, Generalized secret sharing and monotone functions, in “Advances in Cryptology - - - CRYPTO '88”, S. Goldwasser, ed., Lecture Notes in Computer Science 403, pages 27-35, 1989    Non-Patent Document 3: Martin Tompa, Heather Woll, “How to Share a Secret with Cheaters”, Journal of Cryptology, vol. 1, pages 133-138, 1988    Non-Patent Document 4: Wakaha Ogata, Kaoru Kurosawa, Douglas R. Stinson, “Optimum Secret Sharing Scheme Secure Against Cheating”, SIAM Journal on Discrete Mathematics, vol. 20, no 1, pages 79-95, 2006    Non-Patent Document 5: Satoshi Obana and Toshinori Araki, “Almost Optimum Secret Sharing Schemes Secure Against Cheating for Arbitrary Secret Distribution”, Advances in Cryptology - - - Asiacrypt 2006, Lecture Notes in Computer Science 4284, pp. 364-379, 2006    Non-Patent Document 6: Toshinori Araki, “Efficient (k, n) Threshold Secret Sharing Schemes Secure Agianst Cheating from n−1 Cheaters”, Proceedings of ACISP 2007, Lecture Notes in Computer Science 4586, pp. 133-142, 2007    Non-Patent Document 7: Satoshi Obana, “General Making Method of Safe Secret Sharing Scheme against n−1 Cheaters”, Symposium on Cryptography and Information in 2008, SCIS 2008 Publication, 2008
There are following issues generated with Non-Patent Documents 1 to 7 described above. That is, there may be a case where several people managing distributed information conspire together to improve secret information that is to be restored by a single restorer. Specifically, secret information is distributed into n-pieces of distributed information by making (k−1)-degree polynomial, those pieces of distributed information are managed by being distributed to two or more administrators to be managed, and the distributed information is collected from k−1 people to restore the secret information. To improve the secret information restored by a single restorer (referred to as a proper user hereinafter), the conspirers partially restore the (k−1)-degree polynomial based on the distributed information held by themselves, manipulate the distributed information held by themselves, rewrite the manipulated distributed information to a (k−1)-degree polynomial containing the distributed information held by the proper user from the original (k−1)-degree polynomial, and give the manipulated distributed information to the proper user.
When the proper user restores the secret information by having the distributed information included in the distributed information held by the user oneself, the secret information different from the original secret information is restored since the (k−1)-degree polynomial used for restoration is rewritten.
However, there is no means for detecting whether or not the restored secret information is being manipulated taken in the techniques of Non-Patent Documents 1 to 7 described above, so that the restore (proper user) who does not intend cheating cannot restore the secret information.
Further, there is also no technical means taken in the techniques disclosed in Patent Document 1 to 4 for overcoming the issues generated in Non-Patent Documents 1 to 7.
It is an object of the present invention to provide a secret information distribution system, a secret information distributing method and a program thereof for detecting whether or not the restored secret information is being manipulated when those who hold distributed secret information conspire to manipulate the distributed information.